public class Main
{
    /**
     * 简写单词
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNext()) { // 注意 while 处理多个 case
//            String[] strs = in.nextLine().split(" ");
//            StringBuffer sb = new StringBuffer();
//            for (String str : strs) {
//                String s = str.toUpperCase();
//                sb.append(s.charAt(0));
//            }
//            System.out.println(sb.toString());
//        }
//    }

    /**
     * 滑动窗口题目
      */
//    public static Read in = new Read();
//    public static void main(String[] args) throws IOException{
//        int n = in.nextInt();
//        int x = in.nextInt();
//        int[] arr = new int[n + 1];
//        for(int i = 1; i <= n; i++) {
//            arr[i] = in.nextInt();
//        }
//        int left = 1, right = 1, retlen = n;
//        int rleft = -1, rright = -1, sum = 0;
//        while(right <= n) {
//            //入窗口
//            sum += arr[right];
//            //判断
//            while(sum >= x) {
//                //更新结果
//                if(right - left + 1 < retlen) {
//                    rright = right;
//                    rleft = left;
//                    retlen = right - left + 1;
//                }
//                //出窗口
//                sum -= arr[left++];
//            }
//            right++;
//        }
//        System.out.println(rleft + " " + rright);
//    }

    /**
     * 除2 优先级队列 +  贪心
     */
//    public class Main{
//        public static Read read = new Read();
//        public static void main(String[] args) throws IOException{
//            int n = read.nextInt();
//            long k = read.nextLong();
//            PriorityQueue<Long> queue = new PriorityQueue<>((a,b)->{
//                //大根堆
//                return Long.compare(b, a);
//            });
//            for(int i = 0; i < n; i++) {
//                queue.add(read.nextLong());
//            }
//            //贪心 + 优先级队列
//            long ret = 0;
//            while(!queue.isEmpty()) {
//                long x = queue.poll();
//                if(x % 2 == 0 && k > 0) {
//                    queue.add(x / 2);
//                    k--;
//                }else{
//                    ret += x;
//                }
//            }
//            System.out.println(ret);
//        }
//    }

/**
 * 使用滚动数组来标记离n最近的两个斐波那契数
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                int b = 0;
//                int c = 1;
//                while (c < n) {
//                    int a = c;
//                    c = c + b;
//                    b = a;
//                }
//                System.out.println(Math.min(c - n, n - b));
//            }
//        }
//    }


    import java.util.*;

/**
 * 单词搜索---典型的神搜问题
 */
//    public class Solution {
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param board string字符串一维数组
//         * @param word string字符串
//         * @return bool布尔型
//         */
//        boolean[][] visi;
//        char[] word;
//
//        public boolean exist (String[] board, String _word) {
//            // write code here
//            int n = board.length;
//            int m = board[0].length();
//            word = _word.toCharArray();
//            visi = new boolean[n][m];
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    if (board[i].charAt(j) == word[0]) {
//                        visi[i][j] = true;
//                        if(dfs(board, i, j, 0)) return true;
//                        visi[i][j] = false;
//                    }
//                }
//            }
//            return false;
//        }
//        int[] dx = {0, 0, -1, 1};
//        int[] dy = {1, -1, 0, 0};
//        boolean dfs(String[] board, int i, int j, int pos) {
//            int n = word.length;
//            if (pos >= n - 1) {
//                return true;
//            }
//            for (int k = 0; k < 4; k++) {
//                int x = dx[k] + i;
//                int y = dy[k] + j;
//                if (x >= 0 && x < board.length && y >= 0 && y < board[0].length() &&
//                        visi[x][y] == false && board[x].charAt(y) == word[pos + 1]) {
//                    visi[x][y] = true;
//                    if(dfs(board, x, y, pos + 1)) return true;
//                    //回溯
//                    visi[x][y] = false;
//                }
//            }
//            return false;
//        }
//    }
    /**
     * 腐烂的苹果
     */
//    import java.util.*;
//
//
//    public class Solution {
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param grid int整型ArrayList<ArrayList<>>
//         * @return int整型
//         */
//        public int rotApple (ArrayList<ArrayList<Integer>> grid) {
//            // write code here
//            int m = grid.size();
//            int n = grid.get(0).size();
//            boolean[][] visi = new boolean[m][n];//用这个来标记被感染过的1
//            Queue<int[]> queue = new LinkedList<>();
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (grid.get(i).get(j) == 2) {
//                        queue.offer(new int[] {i, j});
//                    }
//                }
//            }
//            //bfs
//            int ret = 0;
//            int count = queue.size();
//            int[] dx = {0, 0, -1, 1};
//            int[] dy = {1, -1, 0, 0};
//            while (!queue.isEmpty()) {
//                while (count > 0) {
//                    count--;
//                    //先遍历当前层的所有元素---下一层的元素先不遍历 先保存到queue
//                    int[] cur = queue.poll();
//                    int a = cur[0];
//                    int b = cur[1];
//                    for (int k = 0; k < 4; k++) {
//                        int x = a + dx[k];
//                        int y = b + dy[k];
//                        if (x >= 0 && x < m && y >= 0 && y < n && grid.get(x).get(y) == 1 &&
//                                visi[x][y] == false) {
//                            queue.offer(new int[] {x, y});
//                            visi[x][y] = true;
//                        }
//                    }
//                }
//                count = queue.size();
//                ret++;
//            }
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (grid.get(i).get(j) == 1 && visi[i][j] == false) {
//                        return -1;
//                    }
//                }
//            }
//            return ret - 1;
//        }
//    }
/**
 * 杨辉三角
 */
//    import java.util.Scanner;
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                int[][] dp = new int[n + 1][n + 1];
//                dp[1][1] = 1;
//                for(int i = 2; i <= n; i++) {
//                    for(int j = 1; j <= i; j++) {
//                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
//                    }
//                }
//                //打印
//                for(int i = 1; i <= n; i++) {
//                    for(int j = 1; j <= i; j++) {
//                        //打印j 个数
//                        StringBuilder ret = new StringBuilder();
//                        int len = Integer.toString(dp[i][j]).length();
//                        for(int k = 0; k < 5 - len; k++) {
//                            //将剩下的域添加到数前面
//                            ret.append(" ");
//                        }
//                        System.out.print(ret.toString() + dp[i][j]);
//                    }
//                    //换个行
//                    System.out.println();
//                }
//            }
//        }
//    }





}
